#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid);
};

// 动态方程：dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
int Solution::minPathSum(vector<vector<int>>& grid) {
    int verticalSize = grid.size(), horizontalSize = grid[0].size();
    int dp[verticalSize][horizontalSize]; // = {0}; // error: variable-sized object may not be initialized
    dp[0][0] = grid[0][0];
    for(int i = 1; i < verticalSize; ++i) dp[i][0] = grid[i][0] + dp[i - 1][0];
    for(int j = 1; j < horizontalSize; ++j) dp[0][j] = grid[0][j] + dp[0][j - 1];
    for(int i = 1; i < verticalSize; ++i) {
        for(int j = 1; j < horizontalSize; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[verticalSize - 1][horizontalSize - 1];
}

class MinPathSumCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(MinPathSumCheck, testMinPathSum_1) {
    vector<vector<int>>grid({{1,3,1}, {1,5,1}, {4,2,1}});
    EXPECT_TRUE(7 == solution.minPathSum(grid));
}

TEST_F(MinPathSumCheck, testMinPathSum_2) {
    vector<vector<int>>grid({{1,2,3}, {4,5,6}});
    EXPECT_TRUE(12 == solution.minPathSum(grid));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
